package com.lmk.dsa.algorithm.graph;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import com.lmk.dsa.struct.graph.Graph;

/**
 * 图的遍历
 * @author LaoMake
 * @since 1.0
 */
public class GraphTraverse {

    /** 图的引用 */
    private Graph graph;

    /** 顶点个数 */
    private int n;

    /** 访问状态数组 */
    private boolean[] visited;

    /** 记录节点是否相连 */
    private int[] connected;

    /** 遍历结果 */
    private List<Object> vertexes;

    /** 连通分量计数 */
    private int ccount;

    public GraphTraverse(Graph graph) {
        this.graph = graph;
        this.n = graph.vertexSize();
        this.ccount = 0;
        this.visited = new boolean[n];
        this.vertexes = new ArrayList<>(n);

        this.connected = new int[n];
        for (int i = 0; i < n; i++) {
            connected[i] = -1;
        }
    }

    /**
     * 获取连通分量
     * @return
     */
    public int getCcount(){
        return this.ccount;
    }

    /**
     * 判断两个索引的节点是否连通
     * @param v
     * @param w
     * @return
     */
    public boolean isConnected(int v, int w){
        assert v >= 0 && v< n;
        assert w >= 0 && w< n;

        return connected[v] == connected[w];
    }

    /**
     * 深度优先遍历
     * @return
     */
    public List<Object> dfs(){
        for (int i = 0; i < n; i++) {
            if(!visited[i]){
                doDFS(i);
                ccount++;
            }
        }
        return vertexes;
    }

    /**
     * 对指定索引的节点进行深度优先遍历
     * @param index
     */
    private void doDFS(int index){
        vertexes.add(graph.getVertex(index));
        visited[index] = true;
        connected[index] = ccount;
        List<Integer> vs = graph.adjoinVertex(index);
        for (Integer v : vs){
            if(!visited[v]){
                doDFS(v);
            }
        }
    }

    /**
     * 广度优先遍历
     * @return
     */
    public List<Object> bfs(){
        doBFS(0);
        return vertexes;
    }

    /**
     * 对指定索引位置的节点进行广度优先遍历
     * @param index
     */
    private void doBFS(int index){
        // 访问队列
        LinkedList<Integer> queue = new LinkedList<>();
        List<Integer> vs;

        vertexes.add(graph.getVertex(index));
        visited[index] = true;
        queue.offer(index);

        while(!queue.isEmpty()) {
            index = queue.poll();
            vs = graph.adjoinVertex(index);
            for (Integer v : vs){
                if(!visited[v]){
                    vertexes.add(graph.getVertex(v));
                    visited[v] = true;
                    queue.offer(v);
                }
            }
        }
    }

}
